# LeetCode 242、有效的字母异位词
# 一、题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
**注意：**若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104s和t仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
# 二、题目解析
题目讲的是让你判断两个字符串中的字母是否一致，比如 示例1 中，s 包含字母 a、n、g、r、m，而 t 中也包含 a、n、g、r、m ，都是只有这五个字母，并且 频次 相同，只是顺序不同。
看到 频次 这个词，你脑海中第一想法是什么？
没错，就是 哈希表 ！
解法思路很简单。
1、首先先判断两个字符串长度是否相同，不相同直接返回 false
2、然后把 s 中所有的字符出现个数使用 计数器 统计起来，存入一个大小为 26 的数组中（注意题目的说明）
3、最后再来统计 t 字符串，即遍历 t 时将对应的字母频次进行减少，如果期间 计数器 出现小于零的情况，则说明 t 中包含一个不存在于 s 中的字母，直接返回 false。
4、最后检查计数器是否归零。
# 三、参考代码
# 代码一
哈希集合调API讨巧解法
# 题目：LC242. 有效的字母异位词
# 难度：简单
# 作者：闭着眼睛学数理化
# 算法：哈希集合调API讨巧解法
# 代码看不懂的地方，请直接在群上提问
# 导入collections中的Counter计数器类
from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
# 直接获得s和t的计数结果Counter(s)和Counter(t)
# 若两者相等，说明s和t中的元素以及频率完全一致，互为字母异位词
# 若两者不相等，说明s和t中的元素以及频率不完全一致，不是一组有效的字母异位词
# 代码二
哈希集合遍历解法
# 题目：LC242. 有效的字母异位词
# 难度：简单
# 作者：闭着眼睛学数理化
# 算法：哈希集合遍历解法
# 代码看不懂的地方，请直接在群上提问
# 导入collections中的Counter计数器类
from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# 如果两个字符串长度不同，必然不可能构成一组有效的字母异位词，返回False
if len(s) != len(t):
return False
# 使用Counter()计数器，得到两个字符串对应的哈希表
cnt1, cnt2 = Counter(s), Counter(t)
# 遍历cnt1中的键（即某个特定字符）
for ch in cnt1:
# 如果这个字符在cnt1中的频率和在cnt2中的频率不相等
if cnt1[ch] != cnt2[ch]:
# 返回False
return False
# 如果在上述循环中没有返回False，说明这两个字符串互为字母异位词
return True
# 代码三
用列表表示哈希表进行统计
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的字母异位词（LeetCode 242）：https://leetcode.cn/problems/valid-anagram/
class Solution {
public boolean isAnagram(String s, String t) {
// 如果两个字符串的长度都不一致，那么肯定是无法成为字母异位词的
if(s.length() != t.length()){
// 直接返回 false
return false;
}
// 让 a - z 这 26 个字母对应的下标变成 0 - 25 方便存到数组中
// 比如 a 对应的索引就是 0
// b 对应的索引就是 1
int[] table = new int[26];
// 从头到尾遍历字符串 s
for( int i = 0 ; i < s.length() ; i++){
// 把访问的字符转换为整数的形式
// 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0
int index = s.charAt(i) - 'a';
// 那么意味着这个字母出现的频次需要加 1
table[index]++;
}
for( int i = 0 ; i < t.length() ; i++){
// 把访问的字符转换为整数的形式
// 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0
int index = t.charAt(i) - 'a';
// 那么意味着这个字母出现的频次需要减 1
table[index]--;
// 如果说发现这个字母出现的频次小于了 0
// 说明 t 中出现了 s 中不曾用的字母
if(table[index] < 0){
// 那就不是字母异位词
return false;
}
}
// 否则，说明是字母异位词
return true;
}
}
# 2、C++ 代码
class Solution {
public:
bool isAnagram(string s, string t) {
// 如果两个字符串的长度都不一致，那么肯定是无法成为字母异位词的
if(s.length() != t.length()){
// 直接返回 false
return false;
}
// 让 a - z 这 26 个字母对应的下标变成 0 - 25 方便存到数组中
// 比如 a 对应的索引就是 0
// b 对应的索引就是 1
vector<int> table(26, 0);
// 从头到尾遍历字符串 s
for( int i = 0 ; i < s.length() ; i++){
// 把访问的字符转换为整数的形式
// 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0
int index = s[i] - 'a';
// 那么意味着这个字母出现的频次需要加 1
table[index]++;
}
for( int i = 0 ; i < t.length() ; i++){
// 把访问的字符转换为整数的形式
// 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0
int index = t[i] - 'a';
// 那么意味着这个字母出现的频次需要减 1
table[index]--;
// 如果说发现这个字母出现的频次小于了 0
// 说明 t 中出现了 s 中不曾用的字母
if(table[index] < 0){
// 那就不是字母异位词
return false;
}
}
// 否则，说明是字母异位词
return true;
}
};
# 3、Python 代码
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# 如果两个字符串的长度都不一致，那么肯定是无法成为字母异位词的
if len(s) != len(t):
# 直接返回 False
return False
# 让 a - z 这 26 个字母对应的下标变成 0 - 25 方便存到数组中
# 比如 a 对应的索引就是 0
# b 对应的索引就是 1
table = [0] * 26
# 从头到尾遍历字符串 s
for i in s:
# 把访问的字符转换为整数的形式
# 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0
index = ord(i) - ord('a')
# 那么意味着这个字母出现的频次需要加 1
table[index] += 1
for i in t:
# 把访问的字符转换为整数的形式
# 比如访问字母 a，那么 -'a' 之后就是 0，就是 a 对应的索引为 0
index = ord(i) - ord('a')
# 那么意味着这个字母出现的频次需要减 1
table[index] -= 1
# 如果说发现这个字母出现的频次小于了 0
# 说明 t 中出现了 s 中不曾用的字母
if table[index] < 0 :
# 那就不是字母异位词
return False
# 否则，说明是字母异位词
return True
# 复杂度分析
- 时间复杂度：
O(n)，其中n为s的长度。 - 空间复杂度：
O(S)，其中S为字符集大小，此处S = 26。